	Probleme din anul de gratie 1995. Rezolvati ce stiti, dar mai ales ce
nu stiti (!!!).		Rodica Pintea (la solicitarea dl. prof. Emil Onea)
	Raspundeti pe adresa rodica@buc.sfos.ro

             Unu si minus unu
             -----------------
Se considera doi vectori A si B cu cate n (n<=10000) elemente egale cu +1 si -1.
	Problema cere:
	a) Transformarea vectorului A in vectorul B, intr-un numar minim de pasi,
un pas constand in schimbarea semnului a k (1<=k<=100) componente oarecare;
	b) Sa se realizeze aceeasi transformare, un pas constand in schimbarea 
semnului a CEL MULT k (1<=k<=100) componente oarecare.
Intrarea: datele de test se vor citi dintr-un fisier (MINUSUNU.INP) care contine pe 
          mai multe linii mai multe teste, fiecare linie continand cate doua 
          valori n k, reprezentand respectiv numarul de elemente (n) al tablourilor 
          si numarul de schimbari de semne (k) la efectuarea unui pas.
Iesirea : se va face pe ecran si intr-un fisier text (PLUSUNU.OUT) afisandu-se
          numarul de pasi in care se realizeaza transformarea si, la cerere,  
          pasii realizati, prin afisarea succesiva a tabloului A.
     ACM.6. (Triunghiuri intersectate) Se dau doua triunghiuri, fiecare 
reprezentat prin trei perechi de coordonate. Sa se scrie un program care sa 
decida daca cele doua triunghiuri se intersecteaza, daca unul este interior 
celuilalt sau daca sunt izolate unul de altul.
Intrarea: Coordonatele vrfurilor triunghiurilor sunt numere intregi din 
domeniul [-100,100]. Toate vrfurile sunt distincte. Fiecare linie a fisierului
de intrare contine un set de date de intrare (cordonatele vrfurilor, in ordinea 
x1 y1 x2 y2 x3 y3 pentru primul triunghi, urmate de coordonatele similare pentru 
al doilea; in total 12 numere). Liniile se citesc pna se ajunge la EOF.
Iesirea: Pentru fiecare linie de intrare, raspunsul se va da pe o linie sub 
forma unui text care va descrie una din cele trei situatii cerute de problema.
Exemplu:
Pentru fisierul de intrare:
0  0 10  0  0 10  1  1  9  1  1  9
0  0  1  1  2  0  3  0  4  1  5  0
0  0 10  0  0 10  1  1 10  1  1 10
iesirea este:
Un triunghi este interior celuilalt
Nu se intersecteaza
Se intersecteaza

 CAMPURI ENERGETICE
-------------------
	Un robot independent construit astfel incat sa-si  refaca singur 
resursele necesare functionarii prin parcurgerea unor zone speciale ale
planetei "natale" (numite zone energetice) se afla intr-o misiune militara.
	El se afla la marginea unei zone energetice dreptunghiulare de di-
mensiuni M x N (numere naturale mai mici decat 100, date), intra in zona de
pe linia 1 si trebuie sa iasa de pe linia M, deplasarile posibile fiind dintr-o
casuta (i,j) a unei linii in oricare dintre casutele (i+1,j-1),(i+1,j),(i+1,j+1)
ale liniei urmatoare, stiut fiind ca doua stationari pe o aceeasi linie a
dreptunghiului ar conduce la detectarea si distrugerea lui de catre robotul
inamic ce supravegheaza linia respectiva. 
	O deplasare determina un consum de K unitati de energie (K numar
natural intre 1 si 20, dat), iar trecerea printr-o casuta determina adaugarea
la rezerva energetica a robotului a unei cantitati de energie caracteristice
casutei respective. 

	Se mai cunosc:	- rezerva energetica pe care o are robotul inainte 
			de a intra in linia 1 a campului (numar natural mai
			mic decat 1000),
			- potentialele energetice ale tuturor casutelor din
			zona date sub forma a M linii cu cate N nr. intregi
			cu valori absolute mai mici sau egale cu 100.
	Se cer: 	- alegerea unei casute initiale si a unui traseu
			astfel incat parcurgerea sa fie posibila si rezerva
			finala a robotului sa fie maxima;
			- succesiunea de casute scrise ca perechi de numere
			(i,j) despartite intre ele prin cate un spatiu si
			rezerva energetica finala a robotului (cu care a
			terminat misiunea).
EXEMPLU:
	Intrarea:
		2 4			(M si N)
		12			(K)
		100			(rezerva initiala)
		10 10 50 30		(potentialele celulelor campului)
		 0 20 30 40

	Iesirea:
		(1,3) (2,4)
		154
	
OBSERVATIE:	Datele de intrare se gasesc intr-un fisier text 
(conform exemplului) al carui nume se citeste de la tastatura.
		Datele de iesire se scriu pe ecran.
NUMERE APROAPE EGALE
--------------------
	Se da un numar de 2n cifre ( n<=50 ). 
	Sa se construiasca doua numere P si Q, fiecare cu n cifre (folosind toate cele 2n cifre ale numarului dat),
astfel incat modulul diferentei lor sa fie minim.
EXEMPLU
Datele (de la tastatura)
2793
Rezultatele (pe ecran)
P=37
Q=29

                          Acul in carul cu fan
                        ------------------------
    Se da un fisier cu n (n<=1000000) numere intregi intre 0 si n (inclusiv).
Sa se afiseze numarul care lipseste (Observatie: intre 0 si n sunt n+1 numere
intregi, deci intr-adevar unul dintre ele nu apare in fisier.)
Intrare:
    Numerele apar cate unul pe linie, intr-o ordine arbitrara. Numele
Iesire:
    Sa se afiseaze numarul lipsa cu un mesaj corespunzator.

                             Campionat
                           ---------------

                Program sursa:   b.pas sau b.c
                Fisier intrare:  b.dat

    Titlul de "Campioana Absoluta" al unei discipline sportive este disputat
de doua echipe cu forta de joc egala. Pentru desemnarea campioanei,  federa-
tia de specialitate a  hotarat  organizarea unui  turneu in care  intre cele 
doua  echipe sa  aiba loc mai  multe  partide  si sa fie declarata campioana ,
echipa care castiga prima, n partide.
    Analistii sportivi sunt interesati in estimarea sansei pe care o are una
dintre echipe la un moment  dat oarecare al turneului, de a deveni campioana.
    Echipele sunt desemnate cu numerele 1 si 2.  Orice partida se termina cu 
victoria  uneia dintre echipe.  In orice  partida, cele  doua echipe au sanse
egale de castig indiferent de rezultatele din partidele anterioare.  
    Stiindu-se  situatia  turneului la un moment dat, si anume numarul
"i" de partide castigate de prima echipa si numarul "j" de partide castigate 
de a doua echipa, sa se calculeze probabilitatea ca echipa 1 sa castige tur-
neul si sa devina campioana. 
    Fisierul de intrare contine pe fiecare linie cate un set de date sub forma 
de triplete "n i j",  unde n reprezinta  numarul de partide ce trebuie castigate
pentru  a deveni campioana (n<=45), i numarul de partide castigate de echipa 1,
iar j numarul de partide castigate de echipa 2.
    Pentru fiecare set de date trebuie afisata probabilitatea ca echipa  1  sa
devina campioana, sub forma:
    Probabilitatea ca echipa 1 sa devina campioana este:  _______

EXEMPLU:
----------
    Daca fisierul de intrare are urmatorul continut:

3 3 1
3 1 3
5 3 3
2 1 0

    Iesirea trebuie sa arate ca mai jos:
----------------------------------------------------------------------------

      Probabilitatea ca echipa 1 sa devina campioana este:   1.0
      Probabilitatea ca echipa 1 sa devina campioana este:   0.0
      Probabilitatea ca echipa 1 sa devina campioana este:   0.5
      Probabilitatea ca echipa 1 sa devina campioana este:   0.75


                       Poligoane asemenea
                     ------------------------
                Program sursa:  d.pas sau d.c
                Fisier intrare: d.dat

    Despre doua poligoane se spune ca sunt asemenea daca au lungimile laturilor
proportionale. Mai exact doua poligoane  P1 P2 ... Pn,   Q1 Q2 ... Qn  sunt
asemenea daca exista i astfel incat:
 
 [P1 P2]/[Qi Q(i+1)]=[P2 P3]/[Q(i+1) Q(i+2)]= ... =[Pn P1]/[Q(i-1) Qi]

Problema consta in a afla daca doua poligoane sunt asemenea sau nu.
    In fisierul  de intrare se gasesc mai  multe seturi de date;  un set de
date are pe prima linie numarul  n  de varfuri ale celor  doua poligoane, pe
pe urmatoarele n linii perechi de numere reale care reprezinta coordonatele
varfurilor primului poligon, iar pe urmatoarele  n  linii perechi de numere
reale care reprezinta coordonatele varfurilor celui de al doilea poligon.
    Pentru fiecare set de date trebuie afisat mesajul:
           DA
daca cele doua poligoane sunt asemenea; si mesajul:
           NU
daca cele doua poligoane nu sunt asemenea.

EXEMPLU:
---------
    Daca fisierul de intrare are urmatorul continut:

4
-1.0 1.0
-1.0 -1.0
1.0 -1.0
1.0 1.0
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0
3
0.0 0.0
2.0 0.0
1.0 2.0
0.0 0.0
2.0 0.0
1.0 1.0

    Iesirea trebuie sa arate ca mai jos:
----------------------------------------------------------------------------

          DA
          NU

                         Problema Paragrafarii
                        -----------------------
                        Program sursa  : e.pas sau e.c
                        Fisier Intrare : e.dat

  Este data o secventa de cuvinte W1,W2,...Wk de lungimi L1,L2,....Lk, pe care
dorim sa o partitionam in linii de lungime L (pastrand ordinea din secventa).
In cadrul unei linii, cuvintele vor fi separate prin blank-uri pentru care 
marimea optima este b, dar aceasta marime poate fi modificata daca este necesar
(dar fara suprapuneri de cuvinte) astfel incat linia Wi W(i+1)......Wj are exact
lungimea L. Definim costul pentru linia Wi,W(i+1),....Wj (j>i) ca fiind abaterea
totala a dimensiunii blank-ului de la valoarea optima, adica marimea 
(j-i)*abs(d-b) unde d este (L-L1-L(i+1)-....-Lj)/(j-i), adica marimea blank-ului 
pentru aceasta linie. Totusi, daca j=k (adica ultima linie) si d>b atunci costul
este 0.
  Gasiti un algoritm care sa minimizeze costul total pentru partitionarea
multimii de cuvinte W1...Wk in linii de lungime L.  
   
  In fisierul de intrare se afla mai multe seturi de date, pentru fiecare se
specifica pe prima linie numarul de cuvinte, pe urmatoarea linie lungimile 
cuvintelor iar pe urmatoarea lungimea unei linii (L) si marimea optima a blank-ului (b)
  
   Iesirea va avea forma:
  Costul minim este :  _______.

EXEMPLU
--------
    Daca fisierul de intrare are urmatorul continut :
  
9
10 7 4 5 4 6 5 2 3
23 1

    Iesirea trebuie sa arate ca mai jos:

 Costul minim este :  0.
